#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct DQNode
{
    int data;
    struct DQNode *prev; // 前驱指针
    struct DQNode *next; // 后继指针
} DQNode;

typedef struct
{
    DQNode *front; // 队头指针（直接指向第一个元素）
    DQNode *rear;  // 队尾指针（直接指向最后一个元素）
} LinkDeque;

// 1. 初始化双端队列
void InitDeque(LinkDeque &DQ)
{
    DQ.front = DQ.rear = NULL; // 初始化为空
}

// 2. 销毁双端队列
void DestroyDeque(LinkDeque &DQ)
{
    DQNode *p = DQ.front;
    while (p != NULL)
    {
        DQNode *temp = p;
        p = p->next;
        free(temp);
    }
    DQ.front = DQ.rear = NULL; // 避免野指针
}

// 3. 队头入队
bool PushFront(LinkDeque &DQ, int x)
{
    DQNode *newNode = (DQNode *)malloc(sizeof(DQNode));
    if (newNode == NULL)
    {
        printf("Memory allocation failed!\n");
        return false;
    }
    newNode->data = x;
    newNode->prev = NULL;
    newNode->next = DQ.front;

    if (DQ.front == NULL)
    { // 空队列特殊处理
        DQ.front = DQ.rear = newNode;
    }
    else
    {
        DQ.front->prev = newNode; // 原队头前驱指向新结点
        DQ.front = newNode;       // 更新队头指针
    }
    return true;
}

// 4. 队尾入队
bool PushRear(LinkDeque &DQ, int x)
{
    DQNode *newNode = (DQNode *)malloc(sizeof(DQNode));
    if (newNode == NULL)
    {
        printf("Memory allocation failed!\n");
        return false;
    }
    newNode->data = x;
    newNode->next = NULL;
    newNode->prev = DQ.rear;

    if (DQ.rear == NULL)
    { // 空队列特殊处理
        DQ.front = DQ.rear = newNode;
    }
    else
    {
        DQ.rear->next = newNode; // 原队尾后继指向新结点
        DQ.rear = newNode;       // 更新队尾指针
    }
    return true;
}

// 5. 队头出队
bool PopFront(LinkDeque &DQ, int &x)
{
    if (DQ.front == NULL)
    { // 队空判断
        printf("Deque is empty!\n");
        return false;
    }

    DQNode *temp = DQ.front;
    x = temp->data;
    DQ.front = DQ.front->next; // 移动队头指针

    if (DQ.front == NULL)
    { // 如果出队后队列为空
        DQ.rear = NULL;
    }
    else
    {
        DQ.front->prev = NULL; // 新队头前驱置空
    }

    free(temp); // 释放原队头结点
    return true;
}

// 6. 队尾出队
bool PopRear(LinkDeque &DQ, int &x)
{
    if (DQ.rear == NULL)
    { // 队空判断
        printf("Deque is empty!\n");
        return false;
    }

    DQNode *temp = DQ.rear;
    x = temp->data;
    DQ.rear = DQ.rear->prev; // 移动队尾指针

    if (DQ.rear == NULL)
    { // 如果出队后队列为空
        DQ.front = NULL;
    }
    else
    {
        DQ.rear->next = NULL; // 新队尾后继置空
    }

    free(temp); // 释放原队尾结点
    return true;
}

// 7. 获取队头元素
bool GetFront(LinkDeque DQ, int &x)
{
    if (DQ.front == NULL)
    {
        printf("Deque is empty!\n");
        return false;
    }
    x = DQ.front->data;
    return true;
}

// 8. 获取队尾元素
bool GetRear(LinkDeque DQ, int &x)
{
    if (DQ.rear == NULL)
    {
        printf("Deque is empty!\n");
        return false;
    }
    x = DQ.rear->data;
    return true;
}

// 9. 判空操作
bool IsEmpty(LinkDeque DQ)
{
    return (DQ.front == NULL);
}

// 10. 判满操作（链式队列理论上不会满）
bool IsFull(LinkDeque DQ)
{
    return false; // 除非内存耗尽
}

// 打印双端队列内容（队头到队尾）
void PrintDeque(LinkDeque DQ)
{
    if (IsEmpty(DQ))
    {
        printf("Deque is empty\n");
        return;
    }

    printf("Deque [front->rear]: ");
    DQNode *p = DQ.front;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 反向打印（验证前驱指针）
void ReversePrint(LinkDeque DQ)
{
    if (IsEmpty(DQ))
    {
        printf("Deque is empty\n");
        return;
    }

    printf("Deque [rear->front]: ");
    DQNode *p = DQ.rear;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->prev;
    }
    printf("\n");
}

int main()
{
    LinkDeque DQ;
    InitDeque(DQ); // 初始化双端队列

    // 前端操作
    PushFront(DQ, 10);
    PushFront(DQ, 20);
    printf("After front push: ");
    PrintDeque(DQ);   // Deque [front->rear]: 20 10
    ReversePrint(DQ); // Deque [rear->front]: 10 20

    // 后端操作
    PushRear(DQ, 30);
    PushRear(DQ, 40);
    printf("After rear push: ");
    PrintDeque(DQ); // Deque [front->rear]: 20 10 30 40

    // 获取队头和队尾
    int front, rear;
    GetFront(DQ, front);
    GetRear(DQ, rear);
    printf("Front: %d, Rear: %d\n", front, rear); // Front: 20, Rear: 40

    // 前端出队
    int poppedFront;
    PopFront(DQ, poppedFront);
    printf("Popped front: %d\n", poppedFront); // Popped front: 20
    PrintDeque(DQ);                            // Deque [front->rear]: 10 30 40

    // 后端出队
    int poppedRear;
    PopRear(DQ, poppedRear);
    printf("Popped rear: %d\n", poppedRear); // Popped rear: 40
    PrintDeque(DQ);                          // Deque [front->rear]: 10 30

    // 判空和判满测试
    printf("Is empty? %s\n", IsEmpty(DQ) ? "true" : "false");
    printf("Is full? %s\n", IsFull(DQ) ? "true" : "false");

    DestroyDeque(DQ); // 销毁双端队列
    return 0;
}